package com.frx.sort.mergesort;

import java.util.Arrays;

/**
 * Created with IDEA
 *
 * @author: xrf
 * @Date: 2019/10/23
 * @Time: 20:03
 */
public class TestTwo {
    private static int num;
    public static void main(String[] args) {
        int[] arr = {2,7,3,9,8,4,1};
        System.out.println(Arrays.toString(arr));
        mergeSort(arr,0,arr.length-1);
        System.out.println(num);
        System.out.println(Arrays.toString(arr));
    }
    public static void mergeSort(int[] arr,int start,int end){
        if (start >= end){
            return;
        }
        int mid = start + (end-start)/2;
        mergeSort(arr,start,mid);
        mergeSort(arr,mid+1,end);
        merge(arr,start,end,mid);
    }
    public static void merge(int[] arr,int start,int end,int mid){
        int [] newArr = new int[end-start+1];
        int p=0;
        int p1 = start;
        int p2 = mid+1;
        while (p1<=mid && p2<=end){
            if (arr[p1]<arr[p2]){
                newArr[p++] = arr[p1++];
            }else {
                newArr[p++] = arr[p2++];
            }
        }
        while (p1<=mid){
            newArr[p++] = arr[p1++];
        }
        while (p2<=end){
            newArr[p++] = arr[p2++];
        }
        for (int i=0;i<newArr.length;i++){
            arr[start+i] = newArr[i];
        }
    }


}